package com.arron.algorithm.leetcodetop100.双指针;

public class 最长回文子串 {


    public static void main(String[] args) {

        String str = "bb";
        String substring = str.substring(0, str.length());
        System.out.println(substring);

    }


    /**
     * 中心扩散法
     * 时间复杂度 O(N2)
     */
    public String longestPalindrome2(String s) {

        if ( s.length() == 1){
            return s;
        }
        String maxStr = "";
        int maxStrlen = 0;

        for (int i = 1; i < s.length(); i++) {

            //以偶数查找回文字串
            String s1 = find(s, i-1, i);
            //以奇数得形式查找回文子串
            String s2 = find(s, i, i);
            if (Math.max(s1.length(),s2.length()) > maxStrlen){
                maxStrlen = Math.max(s1.length(),s2.length());
                maxStr = s1.length()>s2.length()?s1:s2;
            }

        }
        return maxStr;
    }

    public String find(String str,int left,int right){

       while (right<str.length() && left>=0){

           if (str.charAt(left)!=str.charAt(right)){
               break;
           }

           left--;
           right++;

       }

        return str.substring(left+1,right);
    }








    /**
     * 暴力解法
     *  时间复杂度 O(n3) 空间复杂度 O(1)
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {

        if (s==null || s.length()<2){
            return s;
        }
        //最长的回文子串的长度。
        int maxth = 0 ;
        String res = "";

        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+1; j <= s.length(); j++) {
                String ans = s.substring(i,j);
                if (isPalindrome(chars,i,j-1) && ans.length()>maxth){
                    res = ans;
                    maxth = ans.length();
                }
            }
        }
        return res;
    }

    //判断字符串是否是回文串
    private boolean isPalindrome(char[] chars,int left,int right) {
        while (left<right){
            if (chars[left] != chars[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }




}
